/*
 * @lc app=leetcode id=692 lang=cpp
 *
 * [692] Top K Frequent Words
 */

struct Record {
    Record(const string& s, const int f = 0) : word(s), freq(f) {}
    string word;
    int freq;

};

bool cmp(const Record& l, const Record& r) {
    bool ret;
    if (l.freq > r.freq) {
        ret = true;
    } else if (l.freq < r.freq) {
        ret = false;
    } else {
        ret = l.word.compare(r.word) < 0; 
    }
    return ret;
}
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {

        vector<string> ret;

        bool found = false;
        vector<Record> scores;
        unordered_map<string, int> memo;
        for (auto& w : words) {
            memo[w]++;
        }

        for (auto& it : memo) {
            scores.push_back({it.first, it.second});
        }

        sort(scores.begin(), scores.end(), cmp);

        int cnt = 0;
        for (auto& r : scores) {
            if (++cnt > k) {
                break;
            }
            ret.push_back(r.word);
        }
        return ret;
    }

};

